package data_structures_and_algorithms.tree;

import common.TreeNode;

public class Code_0236_lowestCommonAncestor {
    /**
     * 三种思路：
     *
     * 1、使用Map缓存父节点
     *
     * 2、使用对象记录必要信息
     *
     * 3、分析内在关系
     */



    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return process(root, p, q).ans;
    }
    public Info process(TreeNode node, TreeNode p, TreeNode q){
        if (node == null)
            return new Info(false, false, null);

        Info leftInfo = process(node.left, p, q);
        Info rightInfo = process(node.right, p, q);

        boolean findP = (node == p) || leftInfo.findP || rightInfo.findP;
        boolean findQ = (node == q) || leftInfo.findQ || rightInfo.findQ;
        TreeNode ans = null;
        if (leftInfo.ans != null){
            ans = leftInfo.ans;
        }else if (rightInfo.ans != null){
            ans = rightInfo.ans;
        }else {
            if (findP && findQ){
                ans = node;
            }
        }
        return new Info(findP, findQ, ans);
    }

    public class Info{
        public boolean findP;

        public boolean findQ;

        public TreeNode ans;

        public Info(boolean findP, boolean findQ, TreeNode ans){
            this.findP = findP;
            this.findQ = findQ;
            this.ans = ans;
        }
    }

    // 再琢磨这个实现：左神的实现比较好理解
    public class Better{
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            return process(root, p, q);
        }
        public TreeNode process(TreeNode node, TreeNode p, TreeNode q){
            if (node == null)
                return null;
            if (node == p || node == q)
                return node;
            TreeNode leftNode = process(node.left, p, q);
            TreeNode rightNode = process(node.right, p, q);

            TreeNode ans = null;
            if (leftNode == null){
                ans = rightNode;
            }else if (rightNode == null){
                ans = leftNode;
            }else {
                if (leftNode != null && rightNode != null){
                    ans = node;
                }
            }
            return ans;
        }
    }

}
